


#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
 
class Solution
{
public:
    typedef TreeNode TNode;
    vector<int> preorderTraversal1(TreeNode* root)
    {
        if (nullptr == root)
            return vector<int>();

        vector<int> v;
        _dfs(root, v);

        return v;
    }

    vector<int> preorderTraversal2(TreeNode* root)
    {
        if (!root)
            return vector<int>();

        vector<int> vi;
        stack<TNode*> st;
        st.push(root);

        while (!st.empty())
        {
            TNode* cur = st.top();
            st.pop();

            vi.push_back(cur->val);
            if (cur->right)
                st.push(cur->right);
            if (cur->left)
                st.push(cur->left);
        }

        return vi;
    }

    string makeSmallestPalindrome1(string s)
    {
        int sz = s.size();
        char midch = 0;
        string s1 = s.substr(0, sz / 2);
        string s2;

        s2 = s.substr(0 == sz % 2 ? sz / 2 : sz / 2 + 1);
        if (1 == sz % 2)
            midch = s[sz / 2];

        reverse(s2.begin(), s2.end());
        for (int i = 0; i < s1.size(); ++i)
        {
            if (s1[i] != s2[i])
                s1[i] < s2[i] ? s2[i] = s1[i] : s1[i] = s2[i];
        }
        reverse(s2.begin(), s2.end());

        if (midch)
            return s1 + midch + s2;

        return s1 + s2;
    }

    string makeSmallestPalindrome2(string s)
    {
        int left = 0, right = s.size() - 1;

        while (left < right)
        {
            if (s[left] != s[right])
                s[left] > s[right] ? s[left] = s[right] : s[right] = s[left];
            ++left;
            --right;
        }

        return s;
    }

private:
    void _dfs(TNode* root, vector<int>& v)
    {
        if (nullptr == root)
            return;

        v.push_back(root->val);
        _dfs(root->left, v);
        _dfs(root->right, v);
    }
};

int main()
{


	return 0;
}